package leetcode;


public class problems_010 {

    public static void main(String[] arge){
        System.out.println(isMatch("aaaaaaaaaaaaaaaaaaaaaab","a*"));
    }

    static int[][] rs;
    public static boolean isMatch(String s, String p) {
        if(s==null||p==null) return false;
        rs = new int[s.length()+1][p.length()+1];
        return getRs(0,0,s, p);
    }

    public static boolean getRs(int i,int j,String s, String p) {
        if(j==p.length()) return i==s.length();
        if(rs[i][j]!=0) {
            System.out.println(i+" "+j+" "+rs[i][j]);
            return rs[i][j]==1?true:false;
        }
        boolean first = i<s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
        boolean f;
        if(j+1<p.length() && p.charAt(j+1) == '*') {
            f = getRs(i,j+2,s,p) || first && getRs(i+1,j,s,p);
        }else {
            f = first && getRs(i+1,j+1,s,p);
        }
        rs[i][j] = f?1:-1;
        return f;
    }
}
